The invention relates generally to blending operations on objects described in a page description language and, more particularly, to blending operations using planar map representations of those objects.
A page description language (PDL) is a high level, output device independent language for describing objects to be displayed on an output device. The POSTSCRIPT and PORTABLE DOCUMENT FORMAT (PDF) languages are well-known high level page description languages. Both POSTSCRIPT and PORTABLE DOCUMENT FORMAT are trademarks of Adobe Systems Incorporated of San Jose, Calif.
A PDL representation of a document (stored as a file) consists of a series of instructions and possibly images. Instructions are the commands defined in the chosen PDL. For example, one series of instructions may draw a line from point-x to point-y on a page. Images are raster representations of data. For example, an image may be a sampled photograph.
A PDL interpreter converts a PDL file from a series of instructions and images into a display list. A display list is a series of paths. A path defines a shape, a trajectory, and regions of all sorts. Paths may be composed of straight and curved line segments which may, or may not, connect to one another. A path's topology is unrestricted: it may be concave or convex; it may contain multiple closed subpaths, forming several distinct areas; and it may intersect with itself in arbitrary ways. Paths have three fundamental attributes: color; stroke; and fill. If a path is stroked, a line of some specified thickness and color is drawn along its boundary. If a path is filled, the current color or pattern is used to paint the entire area enclosed by the path. Images are described as a rectangular array of sample values.
Paths in a display list may lie in any arbitrary position on a page and may overlap one another. As shown in FIG. 1, the physical representation 100 of two overlapping circular paths (105 and 110) can generate three regions (115, 120, and 125). The display list representation 130 corresponding to the physical representation 100 can be represented by a list, path 1 105 and path 2 110, where the description of path 1 105 and path 2 110 includes information associated with their physical location on a page.
If more than two objects (paths) are present, the graphical processing system must be able to determine which parts of which paths overlap. One technique to represent a series of overlapping paths is known as planar mapping. A planar map is a list of non-overlapping regions that represent the original overlapping paths. For example, the planar map representation 135 of overlapping paths 1 and 2 (see 100) is a list of three non-overlapping paths; one path for each region 115, 120, and 125. A benefit of the planar map representation is that once the display list 130 is transformed into a planar map 135, no further calculations need be performed to determine which paths overlap. In a planar map no two paths overlap. For information on planar map representations see Gangnet et al., "Incremental Computation of Planar Maps," ACM SIGGRAPH '89 Conference Proceedings, Vol. 23, No. 3, 1989, and Preparata and Shamos, "Computational Geometry: An Introduction," Springer-Verlag, New York, 1985.